#include <stdio.h>
#include <stdlib.h>

struct tree
{
  struct tree* left;
  struct tree* right;
  int data;
};

void create_tree(struct tree**,int);
void pre(struct tree*);
void del_data(struct tree**,int);

int main()
{
  struct tree* t;
  t = NULL;
  create_tree(&t,2);
  create_tree(&t,3);
  create_tree(&t,1);
  pre(t);
  printf("\n");
  del_data(&t,2);
  pre(t);
  printf("\n");
  del_data(&t,1);
  pre(t);
  printf("\n");
  del_data(&t,3);
  pre(t);
  printf("\n");
  return 0;
}

void create_tree(struct tree** t,int data)
{
  if(*t == NULL)
  {
    *t = malloc(sizeof(struct tree));
    (*t)->data = data;
    (*t)->left = (*t)->right = NULL;
    return;
  }
  
  if((*t)->data > data)
  {
    create_tree(&(*t)->left,data);
  }

  if((*t)->data < data)
  {
    create_tree(&(*t)->right,data);
  }

}
void pre(struct tree* t)
{
  if(t == NULL)
  {
    return;
  }

  printf("%d ",t->data);
  pre(t->left);
  pre(t->right);
}

void del_data(struct tree** t,int data)
{
  if(*t == NULL)
  {
    printf("no find\n");
    return;
  }

  if((*t)->data > data)
  {
    del_data(&(*t)->left,data);
  }

  else if((*t)->data < data)
  {
    del_data(&(*t)->right,data);
  }
  else
  {
    if((*t)->left)
    {
      struct tree* tmp;
      tmp = (*t)->left;
      while(tmp->right)
      {
        tmp = tmp->right;
      }
      (*t)->data = tmp->data;
      del_data(&(*t)->left,tmp->data);
    }
    else if((*t)->right)
    {
      struct tree* tmp;
      tmp = (*t)->right;
      while(tmp->left)
      {
        tmp = tmp->left;
      }
      (*t)->data = tmp->data;
      del_data(&(*t)->right,tmp->data);
      
    }
    else
    {
      free(*t);
      *t = NULL;
    }
  }
}
